#! /usr/bin/env python 1
# coding:utf-8
# Author: < group 30 >
# Purpose:
# Created: 10/12/2012

import argparse, textwrap, random
import sys
from search import *

class FileError(Exception):
    pass

class TSPState:

    def __init__(self, p):
        self.pathway = p
    
    def __hash__(self):
        return self.__str().__hash__()

    def __str__(self):
        return self.path.__str__()

    def __eq__(self, other):
        return self.pathway == other.pathway

class TSPProblem(Problem):
    
    def __init__(self, plan):
        self.nb_cities, self.plan = read_tsp_plan(plan)
        self.initial = TSPState(self.greedy()) 
    
    def value(self, state):
        p = state.pathway
        c1, c2 = p[0], p[1]
        value = 0

        if c1 > c2 :
            value -= self.plan[c1][c2]
        else:
            value -= self.plan[c2][c1]

        for i in range(2, len(p)):
            c1, c2 = c2, p[i]
            
            if c1 > c2:
                value -= self.plan[c1][c2]
            else:
                value -= self.plan[c2][c1]
        
        return value  

    def greedy(self):
        pathway = [] #range(self.nb_cities)
        r = random.randint(0, self.nb_cities - 1)
        
        picked = {r:1}

        pathway.append(r) 

        for i in range(1, self.nb_cities): # repeat "nb_cities" times the loop
            city = pathway[-1]          # last city in the trip
            current = [-1, sys.maxsize]  # [city number, distance from previous one]

            for j in range(len(self.plan[city])):   # check horizontally (triangle matrix) = check cities before
                if(self.plan[city][j] < current[1] and j != city and j not in picked):
                    current = [j, self.plan[city][j]]

            for k in range(city + 1, self.nb_cities):   # check vertically (triangle matrix) = check cities after
                if(self.plan[k][city] < current[1] and k != city and k not in picked):
                    current = [k, self.plan[k][city]]
                    
            picked[current[0]] = 1
            pathway.append(current[0])
        return pathway

    def successor(self, state):
        for i in range(self.nb_cities):
            for j in range(i+1, self.nb_cities):
                succ = state.pathway[:]
                succ[i], succ[j] = state.pathway[j], state.pathway[i]
                yield ((i, j), TSPState(succ))


def read_tsp_plan(plan):
    
    try:
        fd = open(plan, 'r')
    except:
        raise FileError("Cannot open file")
    
    distances = []
    nb_cities = int(fd.readline())

    for line in fd.readlines():
        d = [float(x) for x in line.split()]
        #for j,d_value in enumerate(line.split(' ')):
        #    print(d_value)
        #    d.append(float(d_value))
        distances.append(d)

    fd.close()
    return nb_cities, distances


if __name__ == "__main__":
    parser = argparse.ArgumentParser(formatter_class = argparse.RawDescriptionHelpFormatter,
            description = textwrap.dedent('''\
                    Assignement 4 : LINGI2261 - Traveling Salesman Problem
                    ------------------------------------------------------
                    '''),
            epilog = "----------------------------------------------------\n---- author : group30 - Crecun Eduard, Gerard Nicolas")
    parser.add_argument("f", action = "store", help = "The file where distances between cities are stored")
    
    args = parser.parse_args()
    

    problem = TSPProblem(args.f)
    node = random_walk(problem)

    print("greedy way : \n")
    print("way : \n", problem.initial.pathway, "\nvalue : \n", problem.value(problem.initial), "\nrandomway :\n")
    print("way : \n", node.state.pathway, "\nvalue : \n", node._value)
